package 我的Java学习_算法基础.day_07;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author 挚爱之夕
 * @date 2021/8/20 - 08 - 20 - 20:19
 * @Description: 我的暑假Java学习.day_07
 * @Version: 1.0
 */
public class _113_全排列_下_ {
    public static void main(String[] args) {
        String s = "abc";
        permutation_prefix("",s.toCharArray());
        System.out.println(list);

        getKPermutation(s,2);
    }
    static int count = 0;//已找到按字典序全排列个数

    /**
     * 前缀法求全排列按字典序的第k位
     * @param s 原串
     * @param k 第k位
     */
    private static void getKPermutation(String s, int k){
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        permutation("",arr,k);
    }
    private static void permutation(String prefix,char[] arr,int k){
        if(prefix.length()==arr.length){    //前缀的长度等于字符串的长度，一个排列就完成了
            count++;
            if(count==k){
                System.out.println("--"+prefix);
                System.exit(0);
            }
            return;
        }
        //每次都从头扫描，只要该字符可用，就附加到前缀后面，前缀变长了
        for(int i = 0;i<arr.length;i++){
            char ch = arr[i];
            //这个字符可用：在pre中出现次数<在字符集中的次数
            if(count(prefix.toCharArray(),ch)<count(arr,ch)){
                permutation(prefix+ch,arr,k);
            }
        }
    }


    private static int count(char[] arr, char ch) {
        int count = 0;
        for(char c:arr){
            if(c==ch) count++;
        }
        return count;
    }


    static ArrayList<String> list = new ArrayList<>();
    private static void permutation_prefix(String prefix, char[] arr){
        if(prefix.length()==arr.length){    //前缀的长度等于字符串的长度，一个排列就完成了
            list.add(prefix);
            return;
        }
        //每次都从头扫描，只要该字符可用，就附加到前缀后面，前缀变长了
        for(int i = 0;i<arr.length;i++){
            char ch = arr[i];
            //这个字符可用：在pre中出现次数<在字符集中的次数
            if(count(prefix.toCharArray(),ch)<count(arr,ch)){
                permutation_prefix(prefix+ch,arr);
            }
        }

    }

}
